import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {

    //
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode tmp = head;
        int count = 0;
        while (tmp != null) {
            count++;
            tmp = tmp.next;
        }

        int n = count / k, m = count % k;
        ListNode[] ans = new ListNode[k];
        ListNode dump = head;
        tmp = head;
        for (int i = 0; i < k; i++) {
            ans[i] = tmp;
            dump = tmp;

            for(int j = 0; j < n - 1; j++){
                if(dump == null) { break;}
                dump = dump.next;
            }
            if(m > 0 && n != 0){
                dump = dump.next;
                m--;
            }
            if(dump == null) { break;}
            tmp = dump.next;
            dump.next = null;
        }
        return ans;
    }

    //
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums){
            set.add(x);
        }

        int ans = 0;
        while(head != null){
            if(set.contains(head.val)){
                while(head != null && set.contains(head.val)){
                    head = head.next;
                }
                ans++;
            }else{
                head = head.next;
            }
        }
        return ans;
    }

    //
    public ListNode removeElements(ListNode head, int val) {
        ListNode dump = new ListNode(-1);
        ListNode cur = dump;
        dump.next = head;

        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dump.next;
    }

    //
    public ListNode modifiedList(int[] nums, ListNode head) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }

        ListNode dump = new ListNode(-1);
        dump.next = head;
        ListNode cur = dump;
        while (cur.next != null) {
            if (set.contains(cur.next.val)) {
                while (cur.next != null && set.contains(cur.next.val)) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dump.next;
    }

    //
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) { return head;}

        ListNode cur = head;
        while(cur.next != null){
            ListNode next = cur.next;
            if(cur.val == next.val){
                cur.next = next.next;
            }else{
                cur = next;
            }
        }
        return head;
    }

    //
    public ListNode deleteDuplicates2(ListNode head) {
        if(head == null || head.next == null) { return head;}

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        while(cur.next != null && cur.next.next != null){
            if(cur.next.val == cur.next.next.val){
                int x = cur.next.val;
                while(cur.next != null && cur.next.val == x){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    //
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode begin = list1, end = list1;
        while(--a > 0){
            begin = begin.next;
        }
        while(b-- > 0){
            end = end.next;
        }

        begin.next = list2;
        while(begin.next != null){
            begin = begin.next;
        }
        begin.next = end.next;
        end.next = null;
        return list1;
    }

    //
    public ListNode removeNodes(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode node = removeNodes(head.next);  //返回的链表头一定是最大的
        if (node.val > head.val) {
            return node;  //删除 head
        }
        head.next = node;  //不删除 head
        return head;
    }
}
